package leetcode.editor.cn.dsa10_recursion;
//泰波那契序列 Tn 定义如下：
// T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
// 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

public class NThTribonacciNumber1137_2 {
    public static void main(String[] args) {
        Solution solution = new NThTribonacciNumber1137_2().new Solution();
        System.out.println(solution.tribonacci(3)); //2
        System.out.println(solution.tribonacci(4)); //4
        System.out.println(solution.tribonacci(25)); //1389537
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * n：2 ->3 ->4 ->5
         * a：0   1   1   2
         * b：1   1   2   4
         * c：1   2   4   7
         * @param n
         * @return
         */
        public int tribonacci(int n) {
            if (n == 0) return 0;
            if (n == 1 || n == 2) return 1;
            int a = 0, b = 1, c = 1;
            int res = 0;
            for (int i = 3; i <= n; i++) {
                res = a + b + c;
                a = b;
                b = c;
                c = res;
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}